#include <gtest/gtest.h>
#include <limits>

#include "algorithm/common/include/common.h"
#include "algorithm/common/include/solve.h"
#include "algorithm/common/include/sortAlgorithm.h"
#include "algorithm/common/include/spiralOrder.h"
#include "algorithm/common/include/subarraySum.h"
#include "algorithm/common/include/summaryRanges.h"
#include "algorithm/common/include/threeSumClosest.h"
#include "algorithm/common/include/topKFrequent.h"
#include "algorithm/common/include/trailingZeroes.h"
#include "algorithm/common/include/utils.h"
#include "algorithm/common/include/wordPattern.h"
#include <vector>

using namespace ::common;
TEST(TestSubArraySum, subArraySumSuits) {
    std::vector<int> a = {3, 4, 7, 2, -3, 1, 4, 2};
    EXPECT_EQ(subarraySum(a, 7), 4);
    a = {1, 1, 1};
    EXPECT_EQ(subarraySum(a, 2), 2);
    a = {1};
    EXPECT_EQ(subarraySum(a, 0), 0);
}

TEST(TestSearch, CommonSuits) {
    std::vector<int> nums = {1};
    EXPECT_EQ(search(nums, 1), 0);
    nums = {4, 5, 6, 7, 0, 1, 2};
    EXPECT_EQ(search(nums, 0), 4);
    EXPECT_EQ(search(nums, 3), -1);
    nums = {1, 3};
    EXPECT_EQ(search(nums, 3), 1);
    nums = {3, 1};
    EXPECT_EQ(search(nums, 3), 0);
    nums = {5, 1, 3};
    EXPECT_EQ(search(nums, 5), 0);
    nums = {4, 5, 6, 7, 0, 1, 2};
    EXPECT_EQ(search(nums, 2), 6);
}

TEST(TestLastRemaining, CommonSuits) { EXPECT_EQ(lastRemaining(5, 3), 3); }
TEST(TestFindNumsAppearOnce, CommonSuits) {
    vector<int> nums = {1, 4, 1, 6};
    vector<int> m_res = findNumsAppearOnce(nums);
    std::vector<int> truth = {4, 6};
    for (int i = 0; i < 2; i++) {

        EXPECT_EQ(m_res[i], truth[i]);
    }
}

TEST(TestTrailingZeroes, CommonSuits) { EXPECT_EQ(trailingZeroes(5), 1); }
TEST(TestStringSplit, CommonSuits) {
    std::string info = "dog cat cat dog";
    std::vector<std::string> result = split(info);
    std::vector<std::string> truth = {"dog", "cat", "cat", "dog"};
    for (int i = 0; i < result.size(); i++) {
        EXPECT_EQ(result[i], truth[i]);
    }
}

TEST(TestWordPattern, CommonSuits) {
    std::string pattern = "abba";
    std::string s = "dog cat cat dog";
    EXPECT_TRUE(wordPattern(pattern, s));
}

TEST(TestCanConstruct, CommonSuits) {
    EXPECT_FALSE(canConstruct("a", "b"));
    EXPECT_FALSE(canConstruct("aa", "ab"));
    EXPECT_TRUE(canConstruct("aa", "aab"));
}

TEST(TestContainsNearbyDuplicate, CommonSuits) {
    std::vector<int> nums = {1, 2, 3, 1};
    EXPECT_TRUE(containsNearbyDuplicate(nums, 3));
    nums = {1, 0, 1, 1};
    EXPECT_TRUE(containsNearbyDuplicate(nums, 1));
    nums = {1, 2, 3, 1, 2, 3};
    EXPECT_FALSE(containsNearbyDuplicate(nums, 2));
}

TEST(TestGetLeastNumbers, CommonSuits) {
    std::vector<int> nums = {6, 5, 2, 3, 8, 3, 1};
    int k = 2;
    std::vector<int> result = getLeastNumbers(nums, 2);
    std::vector<int> truth = {1, 2};
    for (int i = 0; i < k; i++) {

        EXPECT_EQ(truth[i], result[i]);
    }
}

TEST(TestLongestConsecutive, CommonSuits) {
    std::vector<int> nums = {100, 4, 200, 1, 3, 2};
    EXPECT_EQ(longestConsecutive(nums), 4);
    nums = {9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6};
    EXPECT_EQ(longestConsecutive(nums), 7);
}

TEST(TestMinSubArrayLen, CommonSuits) {
    std::vector<int> nums = {2, 3, 1, 2, 4, 3};
    EXPECT_EQ(minSubArrayLen(7, nums), 2);
    nums = {1, 1, 1, 1, 1, 1, 1, 1};
    EXPECT_EQ(minSubArrayLen(11, nums), 0);
    nums = {1, 4, 4};
    EXPECT_EQ(minSubArrayLen(4, nums), 1);
    nums = {1, 2, 3, 4, 5};
    EXPECT_EQ(minSubArrayLen(15, nums), 5);

    nums = {1, 1, 1, 1, 7};
    EXPECT_EQ(minSubArrayLen(7, nums), 1);
}

TEST(TestProductExceptSelf, CommonSuits) {

    std::vector<int> nums = {1, 2, 3, 4};
    std::vector<int> truth = {24, 12, 8, 6};
    std::vector<int> result = productExceptSelfOpt(nums);
    for (int i = 0; i < nums.size(); i++) {

        EXPECT_EQ(truth[i], result[i]);
    }
}

TEST(TestRotate, CommonSuits) {

    std::vector<vector<int>> nums = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    std::vector<vector<int>> truth = {{7, 4, 1}, {8, 5, 2}, {9, 6, 3}};
    rotateFlip(nums);
    for (int i = 0; i < nums.size(); i++) {

        EXPECT_EQ(truth[i], nums[i]);
    }
    nums = {{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}};
    rotateFlip(nums);
    truth = {{15, 13, 2, 5}, {14, 3, 4, 1}, {12, 6, 8, 9}, {16, 7, 10, 11}};

    for (int i = 0; i < nums.size(); i++) {

        EXPECT_EQ(truth[i], nums[i]);
    }
}

TEST(TestSetZeros, CommonSuits) {

    std::vector<vector<int>> nums = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
    std::vector<vector<int>> truth = {{1, 0, 1}, {0, 0, 0}, {1, 0, 1}};
    setZeroes(nums);
    EXPECT_TRUE(valuesIsSame(truth, nums));

    nums = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
    setZeroes(nums);
    truth = {{0, 0, 0, 0}, {0, 4, 5, 0}, {0, 3, 1, 0}};
    EXPECT_TRUE(valuesIsSame(truth, nums));

    nums = {{1, 0}};
    setZeroes(nums);
    truth = {{0, 0}};
    EXPECT_TRUE(valuesIsSame(truth, nums));

    nums = {{1, 0, 3}};
    setZeroes(nums);
    truth = {{0, 0, 0}};
    EXPECT_TRUE(valuesIsSame(truth, nums));
}

TEST(TestSummaryRanges, CommonSuits) {
    std::vector<int> nums = {0, 1, 2, 4, 5, 7};
    std::vector<string> res = summaryRanges(nums);
    vector<string> truth = {"0->2", "4->5", "7"};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth, res);
    }

    nums = {0, 2, 3, 4, 6, 8, 9};
    res = summaryRanges(nums);
    truth = {"0", "2->4", "6", "8->9"};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth, res);
    }

    nums = {-2147483648, -2147483647, 2147483647};
    res = summaryRanges(nums);
    truth = {"-2147483648->-2147483647", "2147483647"};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth, res);
    }
}

TEST(TestDivide, CommonSuits) {
    EXPECT_EQ(divide(19, 3), 6);
    EXPECT_EQ(divide(10, 3), 3);
    EXPECT_EQ(divide(-10, 3), -3);
    EXPECT_EQ(divide(7, -3), -2);
    EXPECT_EQ(divide(1, 1), 1);
    EXPECT_EQ(divide(-2147483648, -1), std::numeric_limits<int>::max());
    EXPECT_EQ(divide(-2147483648, 1), std::numeric_limits<int>::min());
}

TEST(TestFindKthLargest, CommonSuits) {
    vector<int> nums = {4, 6, 2, 1, 8, 7, 3, 9, 0, 5};
    EXPECT_EQ(findKthLargest(nums, 2), 8);
    nums = {3, 2, 1, 5, 6, 4};
    EXPECT_EQ(findKthLargest(nums, 2), 5);
    nums = {3, 2, 3, 1, 2, 4, 5, 5, 6};
    EXPECT_EQ(findKthLargest(nums, 4), 4);
}

TEST(TestIntToRoman, CommonSuits) {
    EXPECT_EQ(intToRoman(3), "III");
    EXPECT_EQ(intToRoman(4), "IV");
    EXPECT_EQ(intToRoman(9), "IX");
}

TEST(TestGenerateParenthesis, CommonSuits) {
    vector<string> res = generateParenthesis(3);
    // vector<string> truth = {"(())", "()()"};
    vector<string> truth = {"((()))", "(()())", "(())()", "()(())", "()()()"};

    for (int i = 0; i < res.size(); i++) {
        EXPECT_EQ(res[i], truth[i]);
    }

    truth = {"()"};
    res = generateParenthesis(1);
    for (int i = 0; i < res.size(); i++) {
        EXPECT_EQ(res[i], truth[i]);
    }
}

TEST(TestSpiralOrder, CommonSuits) {

    std::vector<std::vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    auto res = spiralOrder(matrix);
    vector<int> truth = {1, 2, 3, 6, 9, 8, 7, 4, 5};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth[i], res[i]);
    }

    matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
    res = spiralOrder(matrix);
    truth = {1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth[i], res[i]);
    }

    matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
    res = spiralOrder(matrix);
    truth = {1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth[i], res[i]);
    }

    matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
    res = spiralOrder(matrix);
    truth = {1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10};

    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth[i], res[i]);
    }
    EXPECT_EQ(truth.size(), res.size());
}

TEST(TestReverseBits, CommonSuits) {
    EXPECT_EQ(reverseBits(1), 1 << 31);
    EXPECT_EQ(reverseBits(43261596), 964176192);
}

TEST(TestSortColor, CommonSuits) {
    vector<int> nums = {2, 0, 2, 1, 1, 0};
    vector<int> truth = {0, 0, 1, 1, 2, 2};
    sortColors(nums);
    for (int i = 0; i < nums.size(); i++) {
        EXPECT_EQ(nums[i], truth[i]);
    }
}

TEST(TestSearchRange, CommonSuits) {
    vector<int> nums = {5, 7, 7, 8, 8, 10};
    int target = 8;
    auto res = searchRange(nums, target);
    std::vector<int> truth = {3, 4};
    EXPECT_TRUE(valuesIsSame(res, truth));
    nums = {5, 7, 7, 8, 8, 10};
    truth = {-1, -1};
    res = searchRange(nums, 6);
    EXPECT_TRUE(valuesIsSame(res, truth));

    nums = {1};
    res = searchRange(nums, 1);
    truth = {0, 0};
    EXPECT_TRUE(valuesIsSame(res, truth));

    nums = {2, 2};
    res = searchRange(nums, 2);
    truth = {0, 1};
    EXPECT_TRUE(valuesIsSame(res, truth));
}

TEST(TestNextPermutation, CommonSuits) {
    vector<int> nums = {1, 2, 3, 8, 5, 7, 6, 4};
    nextPermutation(nums);
    vector<int> truth = {1, 2, 3, 8, 6, 4, 5, 7};
    EXPECT_TRUE(valuesIsSame(nums, truth));
    nums = {3, 2, 1};
    truth = {1, 2, 3};
    nextPermutation(nums);
    EXPECT_TRUE(valuesIsSame(nums, truth));
    nums = {1, 1, 5};
    truth = {1, 5, 1};
    nextPermutation(nums);
    EXPECT_TRUE(valuesIsSame(nums, truth));
}

TEST(TestMaximumProduct, CommonSuits) {
    vector<int> nums = {1, 2, 3};
    EXPECT_EQ(maximumProduct(nums), 6);
    nums = {1, 2, 3, 4};
    EXPECT_EQ(maximumProduct(nums), 24);
}
TEST(TestThreeSumClosest, CommonSuits) {
    vector<int> nums = {-1, 2, 1, -4};
    int target = 1;
    EXPECT_EQ(threeSumClosest(nums, target), 2);
    nums = {1, 1, 1, 0};
    target = -100;
    EXPECT_EQ(threeSumClosest(nums, target), 2);
    nums = {4, 0, 5, -5, 3, 3, 0, -4, -5};
    target = -2;
    EXPECT_EQ(threeSumClosest(nums, target), -2);
}

TEST(TestCountSubstrings, CommonSuits) {
    string s = "abc";
    EXPECT_EQ(countSubstrings(s), 3);
}

TEST(TestFindMedianSortedArray, CommonSuits) {
    vector<int> num1 = {1, 3, 4, 9};
    vector<int> num2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    EXPECT_EQ(findKth(num1, num2, 0, num1.size() - 1, 0, num2.size() - 1, 7),
              4);
}
// TEST(TestTopKFrequent, CommonSuits) {
//     vector<int> num1 = {1, 1, 1, 2, 2, 3};
//     vector<int> truth = {1, 2};
//     vector<int> out = topKFrequent(num1, 2);
//     EXPECT_TRUE(valuesIsSame(num1, truth));
//     // EXPECT_EQ(findMedianSortedArrays(num1,num2),);
// }
TEST(TestFindAnagrams, CommonSuits) {
    string s = "cbaebabacd";
    string p = "abc";
    vector<int> out = findAnagrams(s, p);
    vector<int> truth = {0, 6};
    EXPECT_TRUE(valuesIsSame(out, truth));
    s = "aa";
    p = "bb";
    out = findAnagrams(s, p);
    truth = {};
    EXPECT_TRUE(valuesIsSame(out, truth));
}
TEST(TestSolve, CommonSuits) {
    vector<vector<char>> board = {{'X', 'X', 'X', 'X'},
                                  {'X', 'O', 'O', 'X'},
                                  {'X', 'X', 'O', 'X'},
                                  {'X', 'O', 'X', 'X'}};
    vector<vector<char>> truth = {{'X', 'X', 'X', 'X'},
                                  {'X', 'X', 'X', 'X'},
                                  {'X', 'X', 'X', 'X'},
                                  {'X', 'O', 'X', 'X'}};
    solve(board);

    EXPECT_TRUE(valuesIsSame(board, truth));
}

TEST(TestAlgorithm, climbstair) {
    std::vector<int> a = {0, 1, 2, 3, 4, 5, 2, 3, 4};
    EXPECT_EQ(containsDuplicate(a), 1);
}

TEST(TestIsHappy, CommonSuit) {
    EXPECT_TRUE(isHappy(7));
    EXPECT_TRUE(isHappy(1));
}
